package leetcode.code0380;

import java.util.HashMap;
import java.util.Map;

public class RandomizedSet {

	int max = 1 + 2 * (int) 1e5;

	int[] nums;

	Map<Integer, Integer> hash;

	int range;

	public RandomizedSet() {
		nums = new int[max];
		hash = new HashMap<>();
		range = 0;
	}

	public boolean insert(int val) {
		if (hash.containsKey(val)) {
			return false;
		} else {
			hash.put(val, range);
			nums[range++] = val;
			return true;
		}
	}

	public boolean remove(int val) {
		int index = hash.getOrDefault(val, -1);
		if (index == -1) {
			return false;
		} else {
			hash.remove(val);
			if (range > 1 && index != range - 1) {
				int swap = nums[range - 1];
				nums[index] = swap;
				hash.put(swap, index);
			}
			range--;
			return true;
		}
	}

	public int getRandom() {
		return nums[(int) (Math.random() * range)];
	}

}
